package third

/*
	一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

	示例 1:

	输入: [0,1,3]
	输出: 2
	示例 2:

	输入: [0,1,2,3,4,5,6,7,9]
	输出: 8
	 

	限制：

	1 <= 数组长度 <= 10000

*/
func missingNumber(nums []int) int {
	/*
		位运算:遍历nums、每个元素与下标进行按位异或、不为0则说明当前i为缺失的元素
	*/
	nums = append(nums, 0)
	for i := 0; i < len(nums); i++ {
		if i^nums[i] != 0 {
			return i
		}
	}
	return 0
}

func missingNumber2(nums []int) int {
	/*
		二分搜索、给定mid为nums的中间索引、如果nums[mid]==mid,则说明缺失的元素在[mid+1,r],如果不相等,则说明缺失的元素在[l,mid]
	*/
	l, r := 0, len(nums)-1
	for l <= r {
		mid := (l+r)/2
		if mid == nums[mid] {
			l = mid+1
		} else {
			r = mid-1
		}
	}
	return l
}
